Shareware Grab Bag

home *** CD-ROM | disk | FTP | other *** search

/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / prolog.arc / PROLOG.DOC < prev next >

Wrap

Text File | 1985-04-30 | 48.0 KB | 1,732 lines

A.D.A PROLOG Documentation for the Educational and Public Domain Versions Copyright Robet Morein and Automata Design Associates 1570 Arran Way Dresher, Pa. 19025 Technical: (215)-646-4894 Orders: (215)-355-5400 1 Copyright Notice Please be aware of the following: There are two A.D.A. PROLOG products distributed on this disk. The public domain PD PROLOG system has been contributed to the public domain for unrestricted use with one exception: the object code may not be disassembled or modified. Electronic bulletin boards and SIG groups are urged to aid in giving this software the widest possible distribution. The second version is ED PROLOG, an enhanced version of PD PROLOG. It is not in the public domain. If you have purchased ED PROLOG, you have a license to make as many backup copies as you wish. Please understand that unauthorized distribution of this software will result in even less food on the table here at Automata Design Associates. This documentation may be reproduced freely, but may not be included in any other document without the written permission of the author, which you probably will get. 2 Introduction We hope that you'll get some fun out of this PROLOG. It will afford you exposure to THE fifth generation language at the cost only of some intellectual effort. The motive is perfectly explicable: We want you to think of Automata Design Associates for fifth generation software. It also gives us a nice warm feeling. The memory requirement is 192 k. DOS or MSDOS 2.0 are required. There are no features requiring IBM PC architecture. Products by Automata Design Associates There are five versions of PROLOG available from Automata Design Associates. .Public Domain PROLOG This serves to further the general awareness of the public about PROLOG. It also is an excellent adjunct to anyone learning the language. Most of the core PROLOG described by Clocksin and Mellish in the book Programming In PROLOG (1) is implemented. Trace predicates and I/O redirection are not. Memory space is deliberately restricted. We are not angels. .Educational PROLOG At extremely modest cost this affords an educational institution or individual a PROLOG system which provides the maximum available programming area available within the 8086 small programming model. Tracing, a debugging aid, allows monitoring a program as it runs. User settable spy points selectively allow this. Exhaustive tracing is also available. I/O redirection gives some file ability. An "exec" function allows the execution of a program or editor from within PROLOG, thus encouraging an interactive environment. Currently the cost of Educational PROLOG is $29.95. _____ 1. "Programming in Prolog", by Clocksin and Mellish, Springer Verlag, Berlin-Heidelberg-New York, 1981. This is the definitive Prolog reference. Second edition 1984 has a superior presentation but omits some material. 3 .SMF PROLOG A small increment in price adds full random access file capability. Character and structure I/O are allowed. The "asserta and "assertz" predicates are expanded and work with a clause indexing ability. One can assert clauses anywhere in the database under precise pattern matching control. The cost of FSM PROLOG is $49.95 .SMV PROLOG -- Virtual Memory At reasonable cost the addition of virtual memory gives an expansion of capabilities of an order of magnitude. The database on disk is treated transparently. No special provisions need be made by the user. Virtual and resident databases may be mixed. A unique updating algorithim preserves the format of the database as typed by the user while making only those changes necessary to make it equivalent to the database in central memory. The cost of SVM PROLOG is $99.95 .IVM PROLOG At the cost of some speed these versions allow the use of several hundred kilobytes of central memory for clause storage and 64K bytes of stack. Free of the constraints of the 8086 small memory model, it is our intent that the entire library of the Computer Innovations "C" compiler will be brought out in clausal form. Virtual memory is of course included. The cost is a mere $250. .LVM PROLOG For specialized applications, a version is available that accesses the full 1 megabyte address space of the 8086. The cost is $500. 4 To Place Your Order: The phone for orders is (215)-355-5400. Visa, Mastercharge, and American Express are accepted. Technical Information Technical information may be obtained at (215) - 646- 4894 Perhaps we can answer the following questions in advance: There is no support for: APPLE II, Atari, Commodore, or CPM 80 . Other machines from these manufactures may be supported in the future. The public domain version is available from the organizations who distribute such software. It is not available from us. The MSDOS products are available on 5" and 8" diskettes. Returns The software may be returned within 60 days of purchase for a full refund. This applies whether or not the software has been used. We do ask that manuals, disks and packaging be returned in excellent condition. Other Environments Various other machines are targeted for support. The code is written in "C", so it is fairly easy to move. If you are a hardware manufacturer and you would like A.D.A PROLOG to be available for your hardware, contact us at (215)- 646-4894. 5 How to run the Demonstration Programs without Knowing What You're Doing We strongly advise that you purchase the book Programming in PROLOG by Clocksin and Mellish, publisher Springer Verlag, 1981. For the impatient we give some advice. Type the demonstration program you wish to run. There must be at least one entry point within the program. Note: Please understand that these are demonstrations programs. Regarding user interface, they are poorly written. You will probably have to read Clocksin and Mellish to appreciate that the following examples of input are not equivalent: "yes." , "yes" . The animals program - "animal" Most of the examples require C & M for comprehension. The program "animals", however, can be appreciated by anyone. It is a traditional example of an expert system. Run the prolog.exe file. The prompt "?-" will appear. Type "consult( 'animals' ).<CR>". Here <CR> indicates you are to type a carriage return. The PROLOG system will load "animals" and compile it into an internal form. When the "?-" prompt appears PROLOG is ready to run the "animals" guessing game. The object of the program is to deduce the animal you are thinking of. To start it off type "help.<CR>". PROLOG will respond by asking a question. Because of the way the animals program is written, you must respond in a rigid format. You may type "yes<CR>", "no<CR>", or "why<CR>". Eventually the program will terminate with either a guess as to what animal you are thinking of, or a remark that the animal is not within its domain of knowledge. The program has learned, however. You may type "help.<CR>" again to see what effect additional knowledge has on the program's behavior. You may also cause it to forget what it has learned by typeing "forget( user ).<CR>". The Hematology Diagnosis Program - "hemat" Although the logical structure is not as sophisticated as that of "animals", it is interesting for several reasons: 1) The program evaluates numerical data to arrive at a diagnosis. 2) Although inaccurate, it demonstrates that useful question answering systems are not difficult to write in PROLOG. 3) There are some mistakes in the program, which only slightly impede its usefulness. 6 This program uses structure input. Terminate all your answers with a period, as in "y.<CR>", or "no.<CR>". The starting point is "signs.<CR>". PROLOG will prompt you for signs of anemia. The program attempts to diagnose two varieties of a hemolytic anemia. The program could use a good working over by a hematologist and we would be delighted to collaborate. Prime Number Generator - "sieve" This program demonstrates that anything can be programed in PROLOG if one tries hard enough. Asking the question "primes( 50, L ).<CR>" causes a list of prime numbers less than 50 to be printed out. "Sieve" is heavily recursive and quickly exhausts the stack space of the small model interpreters. 7 Running the Interpreter COMMANDS: Give commands in lower case. TO RUN: Invoke PROLOG.EXE. After the "?-" prompt appears, type "consult( <filename><CR> )", where <filename> is the desired database. To exit, type "exitsys.<CR>" TO ASK A QUESTION: At the prompt, type "<expression>.<CR>", where <expression> is a question as described by Clocksin and Mellish. Be sure to terminate the question with a period. The question may be up to 500 characters long. TO INPUT A STRUCTURE AT THE KEYBOARD: The structure may be up to 500 characters in length. Be sure to terminate with a period. TO ASK FOR ANOTHER SOLUTION: If a solution has been provided, the PROLOG interpreter will ask "More? (Y/N):". Only if a "y" is typed will the interpreter perform a search. TO ABORT A SEARCH: Simply type the escape key. The interpreter will respond with "Interrrupted.", and return to the command prompt. TO LOAD ANOTHER DATABASE: Type "consult(<filename>).<CR>" TO REMOVE A DATABASE: Type "forget(<filename>).<CR>" TO EXIT TO THE OPERATING SYSTEM: Type "exitsys.<CR>" The system totally interactive; any commands the operator gives are and must be valid program statements. Statements must terminate with a period. All commands which take a file name also accept a path name. Any name which is not a valid PROLOG atom (refer to C & M) must be enclosed in single quotes. Thus one could say consult( expert ) but one would need single quotes with consult( 'b:\samples\subtype\expert' ). To exit the system, type "exitsys.<CR>" 8 Atoms may contain MSDOS pathnames if they are enclosed by single quotes, ie., '\b:\samples\animal' . You may consult more than one file at a time. However, all names are public and name conflicts must be avoided. The order in which modules are loaded may, in cases of poor program design, affect the behavior. Syntactical Differences There are very few syntactical differences, mostly unrecognized and/or minor. When an operator is declared using the "op" statement, the operator must be enclosed in single quotes in the "op" statement itself, if it would not otherwise be a legal Edinburgh functor. Subsequently, however, the parser will recognize it for what it is, except in the "unop" statement, where it must again be enclosed in single quotes. Variable numbers of functor paramaters is supported. A goal may be represented by a variable, which is less restrictive than the C & M requirement that all goals be functors. The variable must be instantiated to a functor when that goal is pursued. Rules which appear inside other expressions must be enclosed in parenthesis if the "," operator is to be recognized as logical connectives. All operators described by C & M, and user defined infix, prefix, and postfix operators with variable associativity and precedence are supported exactly as in C & M. Please note that operators must be enclosed in single quotes when declared and removed. A name may be up to 250 characters long and may contain the embedded escape sequences \n, \r, and \t if the name is enclosed in single quotes. Arithmetic Signed integer arithmetic is supported. The range is -2 exp( 31 ) to +2 exp( 31 ), or approximately -1073741800 to + 1073741800. Integers may be used as file pointers (model FL and up only.) 9 The Built In Predicate Library The following built in predicates described by Clocksin and Mellish are supported. Those marked with asterisks have additional features: ?- mod arg name asserta nl assertz nonvar atom not atomic put call read clause repeat consult retract ! tab *display true functor var get0 *write integer 10 Description of the Modifications. display- put- write The functions "put", "write", and "display" have been modified to accept multiple arguments. Thus, "put( a, b, c )" would result in the display of "abc". The following built in predicates have been added by A.D.A. and support additional features. Atoms enclosed by single quotest, eg. '\nthis is a new line' can contain the escape sequences '\n', '\r', '\t' and '\''. If these atoms are printed by "display" or "write" they are printed just as they are. If they are printed by the "print" clause they are translated as follows: '\n' results in the printing of a carriage return and a line feed. '\r' results in the printing of a carriage return only. '\t' results in the printing of a tab character. '\'' allows the printing of a single quote within a quoted atom. The "portray" feature is not presently implemented. Description of the New Predicates clearops- Nullify the operator status of every operator in the database. concat( (<variable> | <functor>), <List> ) A list of functors or operators is concatenated into one string, which becomes the name of a new atom to which <variable> or <functor> must match or be instantiated. dir( option ) Provide an alphabetized listing to the console of atoms, constants, or open files. Without options, simply type "dir.<CR>". Options are: dir( pred ) - list clause names only. dir( files ) - list open files only. exitsys 11 Exit to the operating system. forget( <file name> ) Make a database unavailable for use and reclaim the storage it occupied. ratom( <arg>, <stream> )- Read an atom from the input stream, to which <arg> matches or is instantiated. <stream> is optional. If <stream> is not given, the input stream defaults to the standar input. Input is terminated by a CR or LF, which are not included in the stream. 12 Prolog Tutorial Introduction Probably you have heard of the language PROLOG within the last year or so. You probably wondered the following things: 1) What does the name stand for? Names of computer languages are almost always acronyms. 2) What is it good for? 3) Why now? 4) Can I get a copy to play with? Congratulations! You obviously know the answer to the fourth question. We now respond to the other three. 1) The name stands for "programming in logic." This we shall elaborate on in depth later on. 2) PROLOG is good for writing question answering systems. It is also good for writing programs that perform complicated strategies that compute the best or worst way to accomplish a task, or avoid an undesirable result. 3) PROLOG was virtually unknown in this country until researchers in Japan announced that it was to be the core language of that country's fifth generation computer project. This is the project with which Japan hopes to achieve a domainant position in the world information industry of the 1990's. PROLOG is one of the most unusual computer languages ever invented. It cannot be compared to FORTRAN, PASCAL, "C", or BASIC. The facilities complement, rather than replace those of conventional languages. Although it has great potential for database work, it has nothing in common with the database languages used on microcomputers. Perhaps the best point to make is that while conventional languages are prescriptive, PROLOG is descriptive. A statement in a conventional language might read: if( car_wheels = TRUE ) then begin (some sort of procedure) X = X + 1; end 13 A statment in PROLOG could just be a statment of fact about cars and wheels. There are many relationships that hold. For instance, has( car, wheels ). has( car, quant(wheels, four) ). round( wheels ). Each of these statments is an independent fact relating cars, wheels, and the characteristics of wheels. Because they are independent, they can be put into a PROLOG program by programmers working separately. The man who is a specialist on car bodies can say his thing, the wheel specialist can have his say, and the participants can work with relative independence. And this brings to light a major advantage of PROLOG: PARALLEL PROGRAMMING!!! With conventional programming languages projects can still be "chunked", or divided between programmers. But efficiency on a team project drops drastically below that of the individual programmer wrapped up in his own trance. As the number of participants grows the need for communication grows geometrically. The time spent communicating can exceed that spent programming! Although PROLOG does not eliminate the need for task coordination, the problem is considerably simplified. It also provides the ability to answer questions in a "ready to eat form." Consider your favorite BASIC interpreter. Based upon the statements about cars and wheels previously given, could you ask it the following question? has( car, X ), round( X ). Does a car have anything which is round? The question instructs the PROLOG interpreter to consider all the objects that it knows are possessed by a car and find those which are round. Perhaps you are beginning to guess that PROLOG has the abilities of a smart database searcher. It can not only find the facts but selectively find them and interpret them. 14 Consider the problem of a fault tree, as exemplified by this abbreviated one: {Car won't start} | | [Engine turns over](No) --> [Battery voltage](no)-\ (Yes) v | {Check battery} | [Smell gasoline](yes) --> {Try full throttle cranking} | (failure) /--------/ | (details omitted) The fault tree is easily programmed in BASIC. Later we shall show that PROLOG supplies a superior replacement for the fault tree. Though the tree is capable of diagnosing only the problem for which it was designed, PROLOG dynamically constructs the appropriate tree from facts and rules you have provided. PROLOG is not limited to answering one specific question. Given enough information, it will attempt to find all deductive solutions to any problem. 15 PROLOG PRIMER I. Rules and Facts This is where you should start if you know nothing about PROLOG. Let us consider a simple statment in PROLOG, such as: 1) has( car, wheels ). This statement is a "fact. The word "has" in this statment is known either as a functor or predicate. It is a name for the relationship within the parenthesis. It implies that a car has wheels. But the order of the words inside the bracket is arbitrary and established by you. You could just as easily say: 2) has( wheels, car ). and if you wrote this way consistently, all would be well. The words has, wheels, and car are all PROLOG atoms. "Wheels" and "car" are constants. A database of facts can illustrate the data retrieval capabilities of PROLOG. For instance: 3) has( car, wheels ). has( car, frame ). has( car, windshield ). has( car, engine ). You could then ask PROLOG the question: 4) has( car, Part ). The capital "P" of Part means that Part is a variable. PROLOG will make Part equal to whatever constant is required to make the question match one of the facts in the database. Thus PROLOG will respond: Part = wheels. More?(Y/N): If you type "y" the next answer will appear: Part = frame. More?(Y/N): If you continue, PROLOG will produce the answers Part = windshield and Part = engine. Finally, you will see: More?(Y/N):y 16 No. indicating that PROLOG has exhausted the database. Incidentally, when a variable is set equal to a constant or other variable, it is said to be instantiated to that object. Notice that PROLOG searches the database forwards and in this case, from the beginning. The forward search path is built into PROLOG and cannot be changed. An author of a program written in a prescriptive language is quite conscious of the order of execution of his program, while in PROLOG it is not directly under his control. The other major element is the rule which is a fact which is conditionally true. In logic this is called a Horn clause: 5) has( X, wheels ) :- iscar( X ). The fact iscar( car ) and the above rule are equivalent to 6) has( car, wheels). The symbol :- is the "rule sign." The expression on the left of :-is the "head" and on the right is the body. The variable X has scope of the rule, which means that it has meaning only within the rule. For instance, we could have two rules in the database using identically named variables. 7) has( X, transportation ) :- has( X, car ), has( license, X ). 8) has( X, elephant ) :- istrainer( X ), hasjob( X ). The variables X in the two expressions are completely distinct and have nothing to do with each other. The comma between has( X, car ) and has( license, X ) means "and" or logical conjuction. The rule will not be true unless both the clauses has(X, car) and has( license, X ) are true. On the other hand if there is a rule 9) has( license, X ) :- passedexam( X ). consider what PROLOG will do in response to the question: 10) has( harry, transportation ). (Notice that harry has not been capitalized because we do not want it taken as a variable. We could, however, say 'Harry' enclosed in single quotes.) 17 It will scan the database and use (7), in which X will be instantiated to harry. The rule generates two new questions: 11) has( harry, car ). 12) has( license, harry ). Assuming that harry has a car, the first clause of (7) is satisfied and the database is scanned for a match to (12). PROLOG picks up rule (9) in which X is instantiated to harry and the question is now posed: 13) passedexam( harry ). If there is a fact: passedexam( harry ). in the database then all is well and harry has transportation. If there is not, then PROLOG will succinctly tell you: No. But suppose Harry has money and can hire a chauffer as any good programmer can. That could be made part of the program in the following way. The rule which PROLOG tried to use was: 14) has( X, transportation ) :- has( X, car ), has( license, X ). At any point following it there could be included another rule: 15) has( X, transportation ) :- has( X, money ). or simply the bald fact: 16) has( harry, transportation ). These additional rules or facts would be used in two circumstances. If at any point a rule does not yield a solution, PROLOG will scan forward from that rule to find another applicable one. This process is known as "backtracking search" and can be quite time consuming. If in response to the "More?" prompt you answer "y" PROLOG will search for an additional distinct solution. It will attempt to find an alternate rule or fact for the last rule or fact used. If that fails, it will back up to the antecedent rule and try to find an alternate antecedent. And it will continue to back up until it arrives at the question you asked, at which point it will say: 18 No. "Antecedent" to a rule means that it gave rise to its' use. For example, (7) is the antecedent of (9) in the context of the question (16). II. Grammar It is a boring subject, but it must be discussed. All PROLOG statements are composed of valid terms, possibly a rule sign (":- "), commas representing conjunction ("and"), and a period at the very end. A term is a structure, constant, variable, or number. What is a structure? It is a kind of grouping: 1) Structures consist of a functor, and a set of objects or structures in parenthesis. 2) Objects are constants, variables, numbers, or lists, which we have not discussed yet. 3) A constant or functor must be a string of letters and numbers, beginning with a lower case letter, unless you choose to enclose it in single quotes ( 'howdy pardner' ), in which case you are freed from these restrictions. 4) A variable must be a string of letters and numbers beginning with a capital letter. 5) A functor may optionally have arguments enclosed in parenthesis , as in: hascar( X ) or hascar. An example: "has( X, transportation )." is a structure. 19 III. Input / Output You now know enough to write simple databases and interrogate them profitably. But before we examine more sophisticated examples, it will be necessary to add input and output to the language. There are built in functions which appear as rules which are satisfied once. Thus the statment: write( 'Hello world.' ). can be included on the right side of a rule: greetings( X ) :- ishuman( X ), write( 'Hello world.' ). You can also write "write( X )" where X is some variable. Note that 'Hello world.' is not enclosed in double quotes. Single quotes, which denote a constant, are required. Double quotes would denote a list, which is another thing entirely. Provided that a match to "ishuman" can be found, the builtin function "write" is executed and the message printed to the screen. The builtin read( X ) reads a "structure" that you input from the keyboard. More formally, we have read( <variable> or <constant> ) write( <variable> or <constant> ) If you write read( Input ), then the variable "keyboard" will be assigned to whatever is typed at the keyboard, provided that the input is a valid PROLOG structure. The builtin "read" will fail if instead of Keyboard we wrote read( baloney ), where "baloney" is a constant, and the user at the keyboard did not type exactly "baloney." When you input a structure in response to a "read" statement, be sure to end it with a period and an <ENTER>. There is a convenient way of putting the cursor on a new line. This is the builtin "nl". For example: showme :- write( 'line 1' ), nl, write( 'line 2' ). would result in: line 1 line 2 There is also a primitive form of input/output for single characters. It will be discussed later. 20 IV. A Fault Tree Example Consider the "won't start" fault tree for an automobile: {Car won't start} | | [Engine turns over](No) --> [Battery voltage](no)-\ (Yes) v | {Check battery} | [Smell gasoline](yes) --> {Try full throttle cranking} | (failure) /--------/ | | /------------------------/ | | | | | [Check for fuel line leaks](yes)-->{Replace fuel line} | (no) | | | | | [Check for defective carburator](yes)--\ | (no) v | {Repair carburator} \----\ | | [Is spark present](no)-->[Do points open and close](no)-\ | (yes) v /----/ | {Adjust points} | /------------------------/ | | | [Pull distributor wire, observe spark](blue)--\ | (orange) v | | {Check plug wires & cap} | | | [Measure voltage on coil primary](not 12V)--\ | (12V) v | | {Check wiring, ballast resistor} | | | [Check condenser with ohmmeter](conducts)--\ | (no conduction) v | | {Replace condenser} | | | [Open and close points](voltage not 0 - 12)--\ | (voltage swings 0 - 12) v | | {Fix primary circuit} | | | {Consider hidden fault, swap components] | | \-------{Call a tow truck!!} 21 A PROLOG program to implement this is simple. Each statment represents a decision point fragment of the tree. The PROLOG interpreter dynamically assembles the tree as it attempts a solution. 'car wont start' :- write( 'Is the battery voltage low?' ), affirm, nl, write( 'Check battery' ). 'car wont start' :- write( 'Smell gasoline?' ), affirm, nl, 'fuel system'. 'fuel system' :- write( 'Try full throttle cranking' ). 'fuel system' :- write( 'Are there fuel line leaks?' ), affirm, nl, write( 'Replace fuel line.' ). 'fuel system' :- write( 'Check carburator' ). 'car wont start' :- write( 'Is spark present?' ), not( affirm ), nl, 'no spark'. 'no spark' :- write( 'Do points open and close?' ), not( affirm ), nl, write( 'Adjust or replace points.' ). 'no spark' :- write( 'Is the spark off the coil good?' ), affirm, write( 'Check plug wires and cap.' ). 'no spark' :- write( 'What is the voltage on the primary of the coil: ' ), read( Volts ), Volts < 10, nl, write('Check wiring and ballast resistor.'). 'no spark' :- write( 'Does the capacitor leak?' ), affirm, write( 'Replace the capacitor.' ). 'no spark' :- not( 'primary circuit' ). 'primary circuit' :- write( 'Open the points. Voltage across coil?:'), nl, read( Openvolts ), Openvolts < 1, write( 'Close the points. Voltage across coil?:'), read( Closevolts ), Closevolts > 10, nl, write( 'Primary circuit is OK.' ). 22 'no spark' :- write( 'Consider a hidden fault. Swap cap, rotor,points,capacitor.' ). 'Car wont start' :- write( 'Get a tow truck!!' ). --End program-- The above is a simple example of an expert system. A sophisticated system would tell you exactly the method by which it has reached a conclusion. It would communicate by a "shell" program written in PROLOG which would accept a wider range of input than the "valid structure" required by the PROLOG interpreter directly. 23 V. Lists Consider a shopping list given you by your wife. It is a piece of paper with items written on it in an order that probably symbolizes their importance. At the top it may say EGGS!!!, followed by carrots, hamburger, and finally a flea collar for the dog, if you can find one. In PROLOG such a list would be written: 1) [eggs, carrots, hamburger, fleacollar] The order of a list is important so that eggs and carrots cannot be reversed and PROLOG be uncaring. Let us put the list in a structure: shopping( [eggs, carrots, hamburger, fleacollar] ). Then if you wished to isolate the head of the list you could ask the question: shopping( [ Mostimportant | Rest ] ). and PROLOG would respond: Mostimportant = eggs, Rest = [carrots, hamburger, fleacollar]. The vertical bar "|" is crucial here. It is the string extraction operator, which performs a combination of the CDR and CAR functions of LISP. When it appears in the context [X|Y] it can separate the head of the list from the rest, or tail. You may have gained the impression that PROLOG is a rather static language capable of answering simple questions, but it is far more powerful than that. The string extraction operator is the key. It permits PROLOG to whittle a complex expression down to the bare remainder. If the rules you have given it permit it to whittle the remainder down to nothing, then success is achieved. An example of this is the definition of "append." Let us suppose you have not yet done yesterday's shopping, let alone today's. You pull it out of your wallet and sootch tape it to the list your wife just gave you. Yesterday's list was: [tomatoes, onions, ketchup] Combined with [eggs, carrots, hamburger, fleacollar] we obtain [eggs,carrots,hamburger,fleacollar,tomatoes,onions,garlic]. To take one list and to attach it to the tail of another list is to "append" the first to the second. The PROLOG definition of append is: 24 Rule1: append( [], L, L ). Rule2: append( [X|List1], List2, [X|List3] ) :- append( List1, List2, List3 ]. The general scheme is this: The definition consists of one rule and one fact. The rule will be used over and over again until what little is left matches the fact. The [] stands for empty list, which is like a bag without anything in it. This is an example of a recursive definition. Suppose we ask: append( [a,b,c], [d,e,f], Whatgives ). 1. Rule 2 is invoked with arguments ( [a,b,c], [d,e,f], Whatgives ). 2. Rule 2 is invoked again with arguments: ( [b,c], [d,e,f], List3 ). 3. Rule 2 is invoked again with arguments: ( [b], [d,e,f], List3 ). 4. The arguments are now ([], [d,e,f], List3 ). Rule 1 now matches. End. How does this cause a list to be constructed? The key is to watch the third argument. Supplied by the user, it is named "Whatgives". The inference engine matches it to [X|List3] in rule 2. Now lets trace this as rule two is successivly invoked: Whatgives | | | v Rule2: [X|List3] (List3 = [b,c]) | \ | \ | \ v \ Rule2: a [X'|List3'] (List3' = [c]) | \ | \ | \ v \ Rule2: b [X''|List3''] (List3'' = [], ie., empty set.) | \ | \ | \ Rule1: c L ( in Rule1 = [d,e,f] ) End. 25 L in rule 1 is [d,e,f] for the following reason: Notice that rule 2 never alters List2. It supplies it to whatever rule it invokes. So L in rule 1 is the original List2, or [a,b,c]. This example would not have worked if the order of rules one and two were reversed. The PROLOG inference engine always attempts to use the the first rule encountered. You could imagine it as always reading your program from the top down in attempting to find an appropriate rule. Since rule 2 would always satisfy, an unpleasant thing would have happened if the order were reversed. The program would loop forever. I hope that this tiny introduction to PROLOG whets your appetite. You should now purchase the book Programming In Prolog W.F. Clocksin and C.S. Mellish Springer - Verlag Berlin,Heidelberg,New York. 1981,1984 26 26